Increased traffic volumes, new technologies, and stronger competition have put pressure on railway companies to rethink their management strategies and operating practices to use the wealth of information and control capabilities provided by new systems and, in turn, to increase the level of service offered. In particular, the pressure to increase the reliability of shipments and the use of advanced technologies have forced North American railroads to adhere more closely to a scheduled mode of operation.
The overall medium term operating policies to be implemented by the operating personnel (e.g., train dispatchers, yardmasters, trainmasters) are determined at the tactical planning level, which includes train service design (schedule planning), traffic routing and assignment to trains, and track maintenance policy. The term `tactical` is used herein in the sense defined by A. A. Assad, Modelling of Rail Networks. 14B Transportation Research, at 101-114 (1980) and T. Crainic, Rail Tactical Planning: Issues, Models and Tools, (Proceeding of the International Seminar on Freight Transportation Planning and Logistics, Bressanone, Italy, 1987) [hereinafter Crainic-Rail Tactical]. Design of train services or train scheduling at the tactical level consists of the determination of the train's itinerary (origin, destination, major intermediate points, and activity in each of those points), frequency (how many times per day, or per week, the service is offered), and timetable. A timetable provides arrival and departure times for each station (yard) in a train's itinerary.
The main issue involved in tactical train scheduling is a tradeoff between the train arrival/departure times which are driven by the market for transport service (marketing) and/or the need to achieve a fixed amount of work (maintenance, local switching, etc.) in a given period of time, and the reliability of actual schedule performance (i.e., on-time train arrivals) as influenced by the over-the-line and yard delays incurred by trains. Shorter transit times are more attractive to the customers and can result in better equipment utilization; however, these gains can be more than offset by the resulting higher frequency of late train arrivals and the deterioration of the reliability of the transportation service offered to the customer. One cannot overemphasize the importance of on-time shipment arrivals in today's transportation market, and the fact that the trains' schedule performance plays a vital role in the overall reliability of railroad services. See W. B. Allen, M. M. Mahmoud & D. McNeil, The Importance of Time in Transit and Reliability of Transit Time for Shippers, Receivers, and Carriers, 19B Transportation Research, at 447-456 (1985); J. Bouley, Just in Time, 2 Railway Gazette International, February 1987, at 93-95. In practice, train schedulers have almost no means (aside from their past experience) to predict the on-time performance of their new or revised schedules. The adjustments of timetables are usually myopic in nature and dictated by historic train performance; in other words, rather than setting goals, the tactical scheduling function simply reflects the actual train operating practices defined by the oftentimes uncoordinated actions of train and yard dispatchers and engineers.
No existing model of rail operations is appropriate to support the task of tactical rail scheduling as defined above. A large number of the models developed to support railroad operations, (see A. A. Assad, supra, 14B, at 101-114; A. A. Assad, Models For Rail Transportation, 14A Transportation Research, at 205-220 (1980); Crainic-Rail Tactical, supra) can be categorized as either goal or action-oriented, borrowing the classification given by E. K. Morlok, A Goal-Directed Transportation Planning Model, 4 Transportation Research, at 199-213 (1970). Representative of the goal-oriented models are optimization models which, in the context of rail operations, are either network oriented models. See T. Crainic, A Comparison of Two Methods for Tactical Planning in Rail Freight Transportation, at 707-720 (Operational Research '84: Proceedings of the 10th International Conference on Operational Research, Elsevier Publishing Co., New York (1984)), or focus on the real-time operations of a single railway line. While network optimization models are useful in determining yard and blocking policies and train routes, these models do not explicitly deal with schedules; instead they use train frequencies. A notable exception to this statement is work by Morlok and Peterson in E. K. Morlok & R. B. Peterson, Railroad Freight Train Scheduling: A Mathematical Programming Formulation, (The Transportation Center and the Technological Institute, Northwestern University, Evanston, Ill. 1970)) which assigns slots with explicitly stated departure and arrival times to freight trains using binary variables representing the decision whether a specific train is run in a given schedule slot; however, for any real-sized rail network this model is computationally infeasible.
In the real-time category, there are few operational models of optimal line operations (or train dispatching) to date. See R. L. Sauder & W. M. Westerman, Computer Aided Train Dispatching: Decision Support Through Optimization, 13 Interfaces, at 24-37 (1983); P. T. Harker, The Use of Satellite Tracking in Scheduling and Operating Railroads: Models, Algorithms and Applications. (Decision Sciences Department, The Wharton School of the University of Pennsylvania, Philadelphia, Pa., Working Paper 89-04-01, May, 1989). Even if many such real-time systems were available, the short-term scope of such a model would make it impractical for planning purposes. Another problem with the optimization models, both network and line-oriented, is that they are usually based on relatively rigid and simplified mathematical formulations of the problem; at present, it is a challenge just to understand and define all the details involved in the tactical train scheduling problem, let alone produce a detailed mathematical formulation of the problem.
Train dispatching is of crucial importance in the operation of a railroad network because dispatching decisions, through meeting and overtaking delays, greatly influences trains' transit times and on-time performance. According to one study, A. S. Lang & C. D. Martland, Reliability in Railroad Operations: Studies in Railroad Operations and Economics, 8 MIT Report No. R, at 72-74 (Transportation Systems Division, M.I.T., Cambridge, Mass., 1972), 45% of the variance of train arrival times is due to the variance in over-the-line transit times. Unfortunately, dispatchers do not have at their disposal the information that shows system-wide effects of their decisions; their main incentives (besides safety) are to avoid delaying a `hot` high priority train. As reported in Sauder & Westerman, supra. at 24-37, a common response of dispatchers was to clear the low-priority trains into a siding far in advance of incoming high-priority trains, thus minimizing the chance of delaying a `hot` train while causing unnecessary delays to low priority trains. During periods of very dense traffic, this strategy can often backfire; delaying a cluster of low priority trains would soon create an area of congestion in which all trains would be delayed regardless of their priority.
Dispatchers monitor plant (track and trains) status on the visual displays that show train location and switch and signal setting. They can communicate via telephone with train crews, yard personnel, and maintenance-of-way (MOW-track maintenance) personnel. Besides safety and prevention of line-blockage, dispatchers are not given explicit objectives. When resolving train conflicts, dispatchers are guided by fixed train priorities, set by higher management, that remain the same irrespective of whether the train is late, early, or on-time. Once the dispatcher makes a decision of which train is routed onto a siding and which remains on the main track, the actual aligning of switches and clearing of signals is done automatically by specialized, commercially available hardware and software.
Due to a high workload and insufficient information concerning future traffic on their territory and neighboring dispatching territories, dispatchers are forced to cope with incoming traffic as it arrives with little ability to make planes, i.e., the function of a train dispatcher is, now, reactive rather than proactive. Another recent research effort aimed at the reduction of fuel consumption and the increase in the capacity of the railway line is described in I. B. Duncan, K. M. Winch & G. A. Bundell, Driver-Assist-Microprocessor Technology to Aid in the Scheduling of Trains, (T. K. S. Murthy, L. S. Lawrence & R. E. Rivier eds. 1987, Computer in Railway Management, Springer Verlag, Berlin, proceedings of COMPRAIL 87 Conference, Frankfurt, W. Germany) [hereinafter Duncan & Winch]. An implicit-enumeration optimal train dispatching algorithm developed in this project is only one module of a more comprehensive real-time system for control of line-haul railway operations.
Finally, there are reports of two proprietary computer-aided dispatching systems under development: the meet-pass planner developed by Rockwell International as a part of Advanced Railroad Electronics System (ARES) project that attempts to minimize a weighted linear combination of train delay, lateness, and fuel consumption, (See R. D. Burns & D. B. Turner, Safety and Productivity Improvement of Railroad Operations by Advanced Train Control Systems, (Proceedings of 1989 joint IEEE/ASME Railroad Conference, Philadelphia, Pa., April 1989)), and the Union Switch and Signal meet-pass planner that does not have an explicit objective function. See CSX: Welcome to the 21st Century, Railway Age, May, 1989.
The state-of-the-art in optimal train dispatching algorithms can handle only low traffic densities and a short time horizon within a reasonable amount of computational time. See B. Szpigel, Optimal Train Scheduling on a Single Track Railway, at 343-361 (M. Ross ed., Operational Research '72, North Holland, Amsterdam, 1973); Sauder & Westerman, supra, at 24-37; E. R. Petersen, A. J. Taylor & C. D. Montlanol, An Introduction to Computer-Assisted Train Dispatching. 20 Journal of Advanced Transportation, at 63-72 (1986). The only published applicable heuristic algorithm was not empirically tested and can only be used with a linear objective function. See E. R. Petersen & A. J. Taylor, An Optimal Scheduling System for the Welland Canal, 22.3 Transportation Science, at 173-185 (1988). It is interesting to note that almost all published formulations of the problem incorporate only one time variable per train (usually a departure time) and per track segment; such formulations could either lead to infeasible solutions (e.g., a train entering a side track that is still occupied by a preceding train) or to an overly restrictive model in which trains are not allowed to enter a single track segment before the preceding train leaves that segment, although, in the real-world, trains can often follow each other on much shorter headways which depend on the signalling system. See D. Kraay, P. T. Harker & B. Chen, Optimal Pacing of Trains in Freight Railroads: Model Formulation and Solution, (Decision Sciences Department, The Wharton School of the University of Pennsylvania, Philadelphia, Pa., Working Paper 88-03-03, June 1986); D. Jovanovic & P. T. Harker, SCAN: A Decision Support System for Railroad Scheduling, (Impact of Recent Computer Advances on Operations Research: Proceedings of the Conference of the Computer Science Technical Section of the Operations Research Society of America, Williamsburg, Va., January 1989); D. Jovanovic & P. T. Harker, Tactical Scheduling of Rail Operations: The SCAN I Decision Support System, (Decision Sciences Department, The Wharton School of the University of Pennsylvania, Philadelphia, Pa., May 1989), Duncan & Winch, supra; Burns & Turner, supra.; and, Railway Age, supra, May 1989.
There is, therefore, a need for a decision support system for tactical railroad scheduling that meets all of the needs discussed above that is relatively simple to use and is reliable. The present invention achieves these goals.